import collections


class Solution:
    _COLOR = ("R", "Y", "B", "G", "W")  # 颜色列表

    def __init__(self):
        self.hand = collections.Counter()
        self.cache = {}

    def findMinStep(self, board: str, hand: str) -> int:
        self.hand = collections.Counter(hand)
        self.cache[board] = 0
        self.dfs(board)
        return self.cache[""] if "" in self.cache else -1

    def dfs(self, board: str):
        if not board:
            return

        # 剪枝1：如果比已发现的最优解差则直接跳过
        if "" in self.cache and self.cache[board] >= self.cache[""]:
            return

        for color in self._COLOR:
            if self.hand[color] > 0:
                self.hand[color] -= 1
                for i in range(len(board) + 1):
                    # 剪枝2：每种球的添加只有以下两种情况
                    choose = False
                    # 第1种情况：如果前后的球颜色不同，则尝试插入一个后面颜色的球
                    if 0 < i < len(board) and board[i - 1] == board[i] and board[i] != color:
                        choose = True
                    # 第2种情况：如果前后的球颜色相同，则尝试插入一个其他颜色的球
                    if i < len(board) and color == board[i]:
                        choose = True
                    if choose:
                        new = self.clear(board[:i] + color + board[i:])
                        if new not in self.cache or self.cache[new] > self.cache[board] + 1:
                            self.cache[new] = self.cache[board] + 1
                            self.dfs(new)
                self.hand[color] += 1

    def clear(self, board: str):
        """更新桌球（消除需消除的球）"""
        if len(board) < 3:
            return board
        for i in range(len(board)):
            j = i
            while j < len(board) and board[i] == board[j]:
                j += 1
            if j - i >= 3:
                return self.clear(board[:i] + board[j:])
        return board


if __name__ == "__main__":
    print(Solution().findMinStep(board="WRRBBW", hand="RB"))  # -1
    print(Solution().findMinStep(board="WWRRBBWW", hand="WRBRW"))  # 2
    print(Solution().findMinStep(board="G", hand="GGGGG"))  # 2
    print(Solution().findMinStep(board="RBYYBBRRB", hand="YRBGB"))  # 3

    # 测试用例
    print(Solution().findMinStep(board="RRWWRRW", hand="WWRRR"))  # 2

    # 测试用例20
    print(Solution().findMinStep(board="RRWWRRW", hand="WR"))  # -1

    # 测试用例24
    print(Solution().findMinStep(board="WR", hand="WWRR"))  # 4

    # 测试用例28
    print(Solution().findMinStep(board="RRWWRRBBRR", hand="WB"))  # 2

    # 测试用例29
    print(Solution().findMinStep(board="RRWWRRBBR", hand="WB"))  # -1

    # 自制用例
    print(Solution().findMinStep(board="RRYGGYYRRYGGYYRR", hand="GGBBB"))  # 5
